package everydayone.maxProduct;

/**
 * @Date 2020/05/24
 * @author 王光浩
 * @Introduction 通过 DP 来解决这个问题。
 */
public class MyMethodThree {
	public int maxProduct(int[] nums) {
		if (nums == null || nums.length == 0)
			return -1;
		int[] max = new int[nums.length]; // 保存以 i 结尾的最大子数组的乘积
		int[] min = new int[nums.length]; // 保存以 i 结尾的最小子数组的乘积
		int ret = nums[0];
		max[0] = min[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			int m = Math.max(nums[i] * max[i - 1], nums[i] * min[i - 1]);
			int n = Math.min( nums[i] * max[i-1], nums[i] * min[i-1]);
			max[i] = m > nums[i]? m: nums[i];
			min[i] = n < nums[i]? n: nums[i];
			ret = Math.max(ret, max[i]);
		}
		return ret;
	}
}
